/*******************************************************************************
* FileName:         Graph.h
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/12/4 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #12
*******************************************************************************/

#include "Graph.h"  // 引入Graph类的头文件
#include <iostream>
#include <stack>
using namespace std;

Graph::Graph(int max_v):max_count(max_v), adjmax(max_v + 1, vector<int>(max_v + 1, 0)) {}

Graph::~Graph(){
    //STL类自动管理内存
}

void Graph::addedge(int s, int t, int w){
    // 节点ID超出范围
    if(s > max_count || t > max_count){
        cout << "INVALID NODE ID" << endl;
        return;
    }
    //权重为0默认赋值为-1
    if(!w) w = -1;
    adjmax[s][t] = w;
}

int Graph::getV(){
    int count = 0;
    for(int i = 1; i <= max_count; i++){
        bool has_edge = false;
        for(int j = 1; j <= max_count; j++){
            if(adjmax[i][j] != 0 || adjmax[j][i] != 0) {
                has_edge = true;
                break;
            }
        }
        if(has_edge) count++;
    }
    return count;
}

int* Graph::topological(){
    vector<int> indegree(max_count + 1, 0);  // 存储每个节点的入度
    vector<int> res;  // 拓扑排序结果
    stack<int> node;  // 存储入度为0的节点

    // 获取每个节点的入度
    for(int i = 1; i <= max_count; i++){
        for(int j = 1; j <= max_count; j++)
            if(adjmax[j][i] != 0) indegree[i]++;
    }

    // 所有入度为0的节点入栈
    for(int i = 1; i <= max_count; i++){
        if(indegree[i] == 0)
            node.push(i);
    }

    while(!node.empty()){
        int temp = node.top();
        node.pop();
        res.push_back(temp);

        // 更新与当前节点相连的节点的入度
        for(int i = 1; i <= max_count; i++){
            if(adjmax[temp][i] != 0){
                indegree[i]--;
                // 入度变为0，节点入栈
                if(indegree[i] == 0)
                    node.push(i);
            }
        }
    }

    // 图中存在环
    if(res.size() != max_count){
        cout << "THERE EXISTS A LOOP IN THIS GRAPH" << endl;
        return nullptr;
    }

    int* ans = new int[res.size()];
    for(int i = 0; i < res.size(); i++)
        ans[i] = res[i];
    return ans;
}

int* Graph::ka(){
    int *a = topological();  // 获取拓扑排序
    if (a == nullptr) {  // 图中有环
        return nullptr;
    }

    vector<int> topo;  // 存储拓扑排序的节点
    for (int i = 0; i < max_count; i++) {
        topo.push_back(a[i]);
    }

    // 早期开始时间数组
    vector<int> early(max_count + 1, 0);
    for (int i = 0; i < topo.size(); i++) {
        int u = topo[i];
        // 更新每个节点的早期开始时间
        for (int v = 1; v <= max_count; v++) {
            if (adjmax[u][v] != 0) {
                early[v] = max(early[v], early[u] + adjmax[u][v]);
            }
        }
    }

    // 晚期开始时间数组
    vector<int> late(max_count + 1, early[max_count]);
    for (int i = topo.size() - 1; i >= 0; i--) {
        int u = topo[i];
        // 更新每个节点的晚期开始时间
        for (int v = 1; v <= max_count; v++) {
            if (adjmax[u][v] != 0) {
                late[u] = min(late[u], late[v] - adjmax[u][v]);
            }
        }
    }

    // 关键路径
    vector<int> res;
    for (int i = 1; i <= max_count; i++) {
        if (early[i] == late[i]) {
           res.push_back(i);
        }
    }

    int* ans = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        ans[i] = res[i];
    }

    return ans;
}